1. Field of the Invention
The present invention relates generally to the visualization of data, and in particular, to a device and method for visualizing networks by converting network data into a data structure.
2. Description of the Related Art
Data, when presented as rows and columns of numbers and text, is typically raw and undifferentiated. To be useful, raw data must be organized into intelligible categories. Data can also be obscure in the sense that its relevant attributes and relationships are hidden. Normally, the user must conduct an investigation (e.g. by using appropriate data mining tools) to discover such relationships and attributes.
If one presents data in the form of a graph—a representational scheme herein referred to as a “network”—one can supply meaning and context. That is, data—if grouped into relevant categories—can be more easily comprehended. One approach to increasing comprehension of data is data visualization. Data visualization utilizes tools, such as display space plots, to represent data within a display space defined by the coordinates of each relevant data dimensional axis.
Linguists, mathematicians, computer scientists, and others need tools that can visualize networks. Considerable progress has been made in the development of software tools that serve that purpose.
Software tools are known that can be used to create appropriately formatted “trees”. Trees are natural structures that appear in many computer science applications (e.g., data structures, databases, networks, etc.). These software tools usually require textual data input and are able to format trees, make small changes to the nodes and layout, and align nodes. Most of the currently available software tools only produce 2-dimensional (2D) trees. These tools are suited for drawing grammar trees (syntax parse trees), or trees that allow the visual inspection of networks.
Software tools are available that can generate 3-dimensional (3D) tree drawings. An example is the cone tree system from Xerox PARC, as described by George Robertson, Jock Mackinlay, and Stuart Card in “Information visualization using 3D interactive animation”, Communications of the ACM, 1993, 36(4), 57–71. The Xerox PARC cone tree is a 3D radial tree layout presented in Euclidean three-dimensional space.
Another attempt at data visualization through a 3D mapping is illustrated in the CAM Tree developed by Xerox PARC and described by M. Clarkson, in “An Easier Interface”, Byte Magazine, February 1991. The CAM Tree is essentially a three-dimensional tree with limited ability to represent anything more than the hierarchical structure of a data base. The attributes of the data remain hidden.
Traditionally, software tools for visualization of networks portray the respective data in a tree-like format only, as outlined above.
There are other areas where software tools for visualization are employed. Examples are the visualization tools used in connection with high speed logic and circuit simulators, which are used throughout the computer industry in the design of complex systems. The high performance simulators generate enormous amounts of data that are displayed on a screen to allow a user to intervene. An example of such a system is described and claimed in U.S. Pat. No. 5,043,920 entitled “Multi-dimension visual analysis”.
Existing visual presentation systems do not provide a developer or operator means of easily identifying glitches or bottlenecks in complex communication systems. For example, a developer or operator is forced to make inferences concerning the relationships between various types of hardware elements of a network, when these elements are graphically presented on a screen, in order to understand how to improve the respective network.
Another area where networks have become important are site maps on the World Wide Web. Here each page is seen as a node in a network, and the links between the pages are the links in the network. Site maps allow a user to easily navigate through a complex site. In addition, they are useful to mine the information on the World Wide Web, e.g. by analyzing which sites have many incoming or outgoing links, thus identifying authority sites on a certain subject or reference sites.
There are a number of attempts in the literature to solve certain problems which occur when drawing networks (known as graph drawing problems). A recent overview is given in the article “An experimental comparison of four graph drawing algorithms” by Di Battista et. al., Computational Geometry 7, 1997, pp. 303–325. These algorithms are used for 3D-visualization of non-hierarchical networks.
In the article “An algorithm for drawing a hierarchical graph” by R. Tamassia et. al, Int. J. Comput. Geom. Appl. (Singapore) Vol. 6, No. 2 Jun. 1996, pp. 145–155, an algorithm to optimally draw a hierarchical network is described. However, this algorithm uses only a line for each level of hierarchy to arrange the elements and requires the initial placement of elements on the top and bottom hierarchy lines.
The article “GIOTTO3D: a system for visualizing hierarchical structures in 3D” by R. Tamassia et. al., Graph Drawing, Symposium on Graph Drawing, GD '96, Proceedings 1997, pp. 193–198, describes a tool that can arrange a hierarchical network in an optimal 3D-arrangement. A bend-minimization algorithm (from a 2D graph drawing tool) is used.
There are many more areas where visualization tools can be employed since almost all intelligent systems rely heavily on networks and their visualization.
Thus there is a demand for a robust 3D data representation method and system that overcomes problems of known approaches and systems. Such problems include, but are not limited to, the inability to display attributes of data, the limitation of visualizations to tree-like formats, the inability for a user to intuitively identify problems in a visualization, and the lack of detail in hierarchical descriptions of data.